package com.sl.utils;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

/**
 * GPS 抽稀算法
 * @author leixue
 *
 */
public class DouglasUtil {
	private double dMax = 0;
	private int size = 0;
    private int start = 0;
    private int end = 0;
    private ArrayList<LatLngPoint> mLineInit = new ArrayList<LatLngPoint>();
    private ArrayList<LatLngPoint>  mLineFilter = new ArrayList<LatLngPoint>();
    private ArrayList<LngLat> mLine = new ArrayList<>();


    public DouglasUtil(ArrayList<LngLat> mLineInit, double dmax) {
        if (mLineInit == null) {
            throw new IllegalArgumentException("传入的经纬度坐标list == null");
        }
        this.dMax = dmax;
        this.start = 0;
        this.end = mLineInit.size() - 1;
        for (int i = 0; i < mLineInit.size(); i++) {
            this.mLineInit.add(new LatLngPoint(i, mLineInit.get(i)));
        }
    }

    public DouglasUtil(ArrayList<LngLat> mLineInit, double dmax,int size) {
	    	if (mLineInit == null) {
	    		throw new IllegalArgumentException("传入的经纬度坐标list == null");
	    	}
	    	this.mLine = mLineInit;
	    	this.dMax = dmax;
	    	this.start = 0;
	    	this.size = size;
	    	if(mLineInit.size() <= size) {
	    	 	this.end = mLineInit.size() - 1;
	    	}else {
	    		this.end = size;
	    	}
	    
    }

    /**
     * 压缩经纬度点
     *
     * @return
     */
    public ArrayList<LngLat> compress() {
        int size = mLineInit.size();
        ArrayList<LatLngPoint> latLngPoints = compressLine(mLineInit.toArray(new LatLngPoint[size]), mLineFilter, start, end, dMax);
        latLngPoints.add(mLineInit.get(0));
        latLngPoints.add(mLineInit.get(size-1));
        //对抽稀之后的点进行排序
        Collections.sort(latLngPoints, new Comparator<LatLngPoint>() {
            @Override
            public int compare(LatLngPoint o1, LatLngPoint o2) {
                return o1.compareTo(o2);
            }
        });
        ArrayList<LngLat> latLngs = new ArrayList<>();
        for (LatLngPoint point : latLngPoints) {
            latLngs.add(point.lngLat);
        }
        return latLngs;
    }

    /**
     * 压缩经纬度点
     *
     * @return
     */
    public ArrayList<LngLat> compress2() {
    		ArrayList<LngLat> latLngs = new ArrayList<>();
    		compress3(latLngs);
	    	return latLngs;
    }
    /**
     * 压缩经纬度点
     *
     * @return
     */
    private ArrayList<LngLat> compress3(ArrayList<LngLat> latLngs) {
    	
    		this.mLineInit.clear();
	    	for (int i = this.start; i < this.end; i++) {
	    		this.mLineInit.add(new LatLngPoint(i, mLine.get(i)));
	    	}
	    	
	    	int InitSize = this.mLineInit.size();
	    	ArrayList<LatLngPoint> latLngPoints = compressLine(mLineInit.toArray(new LatLngPoint[InitSize]), mLineFilter, 0, InitSize - 1 , dMax);
	    	latLngPoints.add(mLineInit.get(0));
	    	latLngPoints.add(mLineInit.get(InitSize-1));
	    	//对抽稀之后的点进行排序
	    	Collections.sort(latLngPoints, new Comparator<LatLngPoint>() {
	    		@Override
	    		public int compare(LatLngPoint o1, LatLngPoint o2) {
	    			return o1.compareTo(o2);
	    		}
	    	});    	
	    		
	    	if(InitSize < this.size || this.end == mLine.size()) {
//	    		for (int j = 0; j< latLngPoints.size();j++) {
//		    		latLngs.add(latLngPoints.get(j).lngLat);
//		    	}
//	    	}else {
	    		for (int j = 0; j< latLngPoints.size() / 2;j++) {
		    		latLngs.add(latLngPoints.get(j).lngLat);
		    	}
	    		this.start += Math.floor( InitSize / 2);
	    		this.end += Math.floor( InitSize / 2);
	    		if(this.end >= mLine.size()) {
		    		this.end = mLine.size();
		    	}
	    		compress3(latLngs);
	    	}
	    	return latLngs;
    }


    /**
     * 根据最大距离限制，采用DP方法递归的对原始轨迹进行采样，得到压缩后的轨迹
     * x
     *
     * @param originalLatLngs 原始经纬度坐标点数组
     * @param endLatLngs      保持过滤后的点坐标数组
     * @param start           起始下标
     * @param end             结束下标
     * @param dMax            预先指定好的最大距离误差
     */
    private ArrayList<LatLngPoint> compressLine(LatLngPoint[] originalLatLngs, ArrayList<LatLngPoint> endLatLngs, int start, int end, double dMax) {
        if (start < end) {
            //递归进行调教筛选
            double maxDist = 0;
            int currentIndex = 0;
            for (int i = start + 1; i < end; i++) {
                double currentDist = distToSegment(originalLatLngs[start], originalLatLngs[end], originalLatLngs[i]);
                if (currentDist > maxDist) {
                    maxDist = currentDist;
                    currentIndex = i;
                }
            }
            //若当前最大距离大于最大距离误差
            if (maxDist >= dMax) {
                //将当前点加入到过滤数组中
                endLatLngs.add(originalLatLngs[currentIndex]);
                //将原来的线段以当前点为中心拆成两段，分别进行递归处理
                compressLine(originalLatLngs, endLatLngs, start, currentIndex, dMax);
                compressLine(originalLatLngs, endLatLngs, currentIndex, end, dMax);
            }
        }
        return endLatLngs;
    }

    /**
     * 使用三角形面积（使用海伦公式求得）相等方法计算点pX到点pA和pB所确定的直线的距离
     * @param start  起始经纬度
     * @param end    结束经纬度
     * @param center 前两个点之间的中心点
     * @return 中心点到 start和end所在直线的距离
     */
    private double distToSegment(LatLngPoint start, LatLngPoint end, LatLngPoint center) {
        double a = Math.abs(AMapUtils.calculateLineDistance(start.lngLat, end.lngLat));
        double b = Math.abs(AMapUtils.calculateLineDistance(start.lngLat, center.lngLat));
        double c = Math.abs(AMapUtils.calculateLineDistance(end.lngLat, center.lngLat));
        double p = (a + b + c) / 2.0;
        double s = Math.sqrt(Math.abs(p * (p - a) * (p - b) * (p - c)));
        double d = s * 2.0 / a;
        return d;
    }
}
